package com.arron.algorithm.leetcodetop100.动态规划.子序列or子数组;

import java.util.Arrays;

public class 最长递增子序列 {



    //[10,9,2,5,3,7,101,18]
    // 1  1  1 2 2 3 4  4

    public int lengthOfLIS(int[] nums) {

        //用来记录nums中的以nums[i] 结尾的最长的递增子序列
        int[] dp = new int[nums.length];

        Arrays.fill(dp,1);
        int res = 0;
        for (int i = 0; i < nums.length; i++) {

            int temp = 0;
            for (int j = 0; j < i; j++) {

                if (nums[j]<nums[i]){
                    temp = Math.max(temp,dp[j]);
                }

            }
            if (temp!=0){
                dp[i] = temp+1;
            }

            res =  Math.max(res,dp[i]);
        }

        return res;
    }


}
